package leetcode

import (
	"math"
	"math/rand"
	"time"
)

//采用RK字符串匹配法
func longestDupSubstring(s string) string {
	rand.Seed(time.Now().UnixNano())
	//生成两个进制
	a1, a2 := randInt(26, 100), randInt(26, 100)
	//生成两个mod,防止哈希值超过界限，这里取1e9+7是个质数，而且足够大
	mod1, mod2 := randInt(1e9+7, math.MaxInt32), randInt(1e9+7, math.MaxInt32)
	//对子串编码
	arr := []byte(s)
	for _, v := range arr {
		v -= 'a'
	}
	//记录起始位置和长度
	start, length := -1, 0
	//二分查找，其中m表示长度，即选取[0:m]长度的子串进行遍历查找有没有重复的字符串
	l, r := 0, len(s)-1
	for l <= r {
		m := l + (r-l)/2
		index := check(arr, m, a1, a2, mod1, mod2)
		if index != -1 {
			//找到了就变长,并且记录，注意这里不需要做比较判断，反正之后会去验证len更长的情况
			length = m
			start = index
			l = m + 1
		} else {
			//没找到就变短
			r = m - 1
		}
	}
	//没找到
	if start == -1 {
		return ""
	}
	return s[start : start+length]
}

//rk算法匹配字符串
func check(arr []byte, m int, a1 int, a2 int, mod1 int, mod2 int) int {
	am1, am2 := modPow(a1, m, mod1), modPow(a2, m, mod2)
	//计算两个h1,h2,用作哈希值计算的初始值
	var h1, h2 int
	for _, v := range arr[:m] {
		h1 = (h1*a1 + int(v)) % mod1
		h2 = (h2*a2 + int(v)) % mod2
	}
	//记录以及遍历过的哈希值
	seen := map[[2]int]bool{{h1, h2}: true}
	//注意要从1开始，因为匹配的是[0:m]这段
	for i := 1; i <= len(arr)-m; i++ {
		h1 = (h1*a1 - int(arr[i-1])*am1 + int(arr[i+m-1])) % mod1
		//取了模可能会小于0
		if h1 < 0 {
			h1 += mod1
		}
		h2 = (h2*a2 - int(arr[i-1])*am2 + int(arr[i+m-1])) % mod2
		if h2 < 0 {
			h2 += mod2
		}
		//找到了就返回index
		if seen[[2]int{h1, h2}] {
			return i
		}
		//否则添加到记录里
		seen[[2]int{h1, h2}] = true
	}
	return -1
}

func randInt(a, b int) int {
	return a + rand.Intn(b-a)
}

//返回x^n%mod
func modPow(x, n, mod int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n&1 == 1 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}
